package cn.dlc.com.linear;

import lombok.Data;

import java.util.Iterator;

/**
 * @author 邓立川
 * @date 2021/3/17 20:41
 * @desc 单向链表实现
 */

@Data
public class LinkList<T> implements Iterable<T>{

    // 用来存放元素
    private Node<T> head;

    // 元素个数，不是数组长度
    private int N;

    //
    public LinkList(){
        // 初始化数据域是空的，下一个元素也没有，完全是空的
        this.head = new Node(null, null);
        this.N = 0;
    }

    // 置空
    public void clear(){
        this.N = 0;
    }
    // 是否为空
    public boolean isEmpty(){
        return this.N == 0;
    }

    // 顺序表元素个数
    public int length(){
        return this.N;
    }


    // 获取指定位置的内容
    public T get(int i) {

        // 第一个元素
        Node<T> node = head.getNext();

        // 从头到尾的遍历一遍,找到i的位置
        for (int j = 0; j < i; j++) {
            // 先判断是不是空的，因为可能没有元素
            if(node != null) {
                // 依次获取元素
                node = node.getNext();
            } else {
                // i的值过大，不找了
                return null;
            }
        }
        // 返回这个值
        return node.getItem();
    }

    // 指定位置插入元素
    public void insert(int i,T t){
        // 找到i的前一个节点i-1
        Node<T> node = head.getNext();
        for (int j = 0; j < i - 1; j++) {
            if(node != null) {
                node = node.getNext();
            }
        }

        // i处的节点
        Node<T> currentNode = node.getNext();
        // 创建一个新的元素，指向原来的i
        Node<T> newNode = new Node<>(t, currentNode);

        // 重新指向
        node.setNext(newNode);

        // 元素增加
        N++;
    }
    // 最后插入元素
    public void insert(T t){

        // 找到最后一个元素
        Node<T> node = head.getNext();

        if(node == null) {
            // 之前是一个空的链表
            head.setNext(new Node<>(t,null));
            return;
        }

        for (int i = 0; i < N; i++) {
            node = node.getNext();
        }

        // 绑定最后一个元素
        Node<T> lastNode = new Node<>(t, null);
        node.setNext(lastNode);

        N++;
    }

    // 删除指定位置的元素
    public T remove(int i) {
        // 找到i的前一个节点i-1
        Node<T> node = head.getNext();
        for (int j = 0; j < i - 1; j++) {
            if(node != null) {
                node = node.getNext();
            }
        }

        // 当前位置元素，要返回的
        Node<T> currentNode = node.getNext();
        Node<T> newNextNode = node.getNext().getNext();

        // 重新指定下一个元素
        node.setNext(newNextNode);

        return currentNode.getItem();
    }
    // 元素第一次出现的位置
    public int indexOf(T t) {

        // 遍历整个数组
        Node<T> node = head.getNext();
        for (int i = 0; i < N; i++) {
            if(t != null && t.equals(node.getNext())) {
                return i;
            }
        }

        return -1;
    }

    @Override
    public Iterator<T> iterator() {
        return new LIterator();
    }

    private class LIterator implements Iterator{

        private Node<T> node;

        public LIterator(){
            // 初始化
            this.node = head;
        }

        @Override
        public boolean hasNext() {

            return node.getNext() != null;
        }

        // 获取下一个元素，不是获取节点
        @Override
        public Object next() {
            node = node.getNext();
            return node.getItem();
        }
    }

    // 高级应用
    // 高级应用
    // 高级应用
    public void reverse(){

        if(isEmpty()) {
            return;
        }
        reverse(head.getNext());
    }

    public Node<T> reverse(Node<T> node) {
        // 如果到了最后一个节点
        if(node.getNext() == null) {
            // 头结点指向最后这个节点，
            this.head.setNext(node);
            return node;
        }

        // 反转当前节点的下一个节点，并且返回
        Node<T> pre = reverse(node.getNext());
        // 当前节点的下一个节点，变成了当前节点的上一个节点
        pre.setNext(node);
        // 当前节点的下一个节点置为空,等返回的时候重置
        node.setNext(null);

        return node;
    }

    // 获取中间索引位置的值
    public T getMid(){
        Node<T> fast = this.head;
        Node<T> slow = this.head;

        while(fast != null && fast.getNext() != null){
            fast = fast.getNext().getNext();
            slow = slow.getNext();
        }
        return slow.getItem();
    }

    // 是否有环
    private boolean hasCircle(){

        Node<T> fast = this.head;
        Node<T> slow = this.head;
        while(fast != null && fast.getNext() != null){
            fast = fast.getNext().getNext();
            slow = slow.getNext();

            if(fast.equals(slow)) {
                return true;
            }

        }

        return false;
    }
    // 是否有环
    public boolean hasCircle(Node<T> node){

        Node<T> fast = node;
        Node<T> slow = node;
        while(fast != null && fast.getNext() != null){
            fast = fast.getNext().getNext();
            slow = slow.getNext();

            if(fast.equals(slow)) {
                return true;
            }

        }

        return false;
    }

    // 环的入口
    public Node<T> circleEnter(){
        Node<T> fast = this.head;
        Node<T> slow = this.head;
        Node<T> temp = null;
        while(fast != null && fast.getNext() != null){
            fast = fast.getNext().getNext();
            slow = slow.getNext();

            if(fast.equals(slow)) {
                // 表示找到了环了
                temp = this.head;
                // 继续循环，也就是不结束
                continue;
            }
            if(temp != null) {
                // 找到环了,temp也往后走
                temp = temp.getNext();
                if(temp.equals(slow)) {
                    break;
                }
            }
        }

        return temp;
    }

    // 环的入口
    public Node<T> circleEnter(Node<T> node){
        Node<T> fast = node;
        Node<T> slow = node;
        Node<T> temp = null;
        while(fast != null && fast.getNext() != null){
            fast = fast.getNext().getNext();
            slow = slow.getNext();

            if(fast.equals(slow)) {
                // 表示找到了环了
                temp = node;
                // 继续循环，也就是不结束
                continue;
            }
            if(temp != null) {
                // 找到环了,temp也往后走
                temp = temp.getNext();
                if(temp.equals(slow)) {
                    break;
                }
            }
        }

        return temp;
    }


}
